package com.example.arithmeticleetcode.leetcode.jan;


import com.example.arithmeticleetcode.learnArithmetic.priority.queue.heap.BinaryHeap;
import com.example.arithmeticleetcode.learnArithmetic.quque.Quque;

import java.util.*;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2021-01-22 09:48
 **/
public class Demo19 {

    public static boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) return false;
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();
        char[] chars1 = word1.toCharArray();
        for (char c : chars1) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }
        char[] chars2 = word2.toCharArray();
        for (char c : chars2) {
            if (!map1.containsKey(c)) return false;
            map2.put(c, map2.getOrDefault(c, 0) + 1);
        }
        if (map1.size() != map2.size() || map1.values().size() != map2.values().size()) return false;
        for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
            if (!map2.containsKey(entry.getKey())) return false;
            if (!map2.values().contains(entry.getValue())) return false;
        }
        for (Map.Entry<Character, Integer> entry : map2.entrySet()) {
            if (!map1.values().contains(entry.getValue())) return false;
        }
        return true;
    }


    public int numJewelsInStones(String jewels, String stones) {
        if (jewels == null || jewels.length() == 0) return 0;
        if (stones == null || stones.length() == 0) return 0;
        int[] arr = new int[123];
        for (char c : jewels.toCharArray()) {
            arr[c]++;
        }
        int count = 0;
        for (char c : stones.toCharArray()) {
            if (arr[c] > 0) count++;
        }
        return count;
    }

    public boolean rotateString(String A, String B) {
        if (A.length() != B.length()) return false;
        return (B + B).contains(A);
    }

    public String reverseLeftWords(String s, int n) {
        if (n == 0 || n >= s.length()) return s;
        int mod = n % s.length();
        return s.substring(mod) + s.substring(0, mod);
    }


    public String replaceSpaces(String S, int length) {
        char[] chars = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            if (chars[i] == ' ') {
                sb.append("%20");
            } else {
                sb.append(chars[i]);
            }
        }
        return sb.toString();
    }

    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode vNode = new ListNode(-1);
        ListNode curNode = vNode;
        while (head != null) {
            if (!set.contains(head.val)) {
                curNode.next = head;
                curNode = head;
                set.add(head.val);
            }
            head = head.next;
        }
        curNode.next = null;
        return vNode.next;
    }

    public int game(int[] guess, int[] answer) {
        int count = 0;
        for (int i = 0; i < guess.length; i++) {
            if (guess[i] == answer[i]) count++;
        }
        return count;
    }

    public int minCount(int[] coins) {
        int count = 0;
        for (int coin : coins) {
            count += (coin >> 1);
            if ((coin & 1) == 1) count++;
        }
        return count;
    }

    /**
     * 1351. 统计有序矩阵中的负数
     *
     * @param grid
     * @return
     */
    public int countNegatives(int[][] grid) {
        int count = 0;
        for (int[] ints : grid) {
            for (int anInt : ints) {
                if (anInt < 0) {
                    break;
                }
                count++;
            }
        }
        return grid.length * grid[0].length - count;
    }

    /**
     * 1446. 连续字符
     *
     * @param s
     * @return
     */
    public int maxPower(String s) {
        char[] chars = s.toCharArray();
        char pre = chars[0];
        int count = 1;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == pre) {
                count++;
            } else {
                max = Math.max(count, max);
                pre = chars[i];
                count = 1;
            }
        }
        return max;
    }

    /**
     * 1460. 通过翻转子数组使两个数组相等
     *
     * @param target
     * @param arr
     * @return
     */
    public boolean canBeEqual(int[] target, int[] arr) {
        int[] countArr = new int[1001];
        for (int i : target) {
            countArr[i]++;
        }
        for (int i : arr) {
            if (countArr[i] <= 0) return false;
            countArr[i]--;
        }
        return true;
    }

    /**
     * 811. 子域名访问计数
     *
     * @param cpdomains
     * @return
     */
    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (String cpdomain : cpdomains) {
            char[] chars = cpdomain.toCharArray();
            int count = 0;
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == ' ') {
                    count = Integer.parseInt(new String(chars, 0, i));
                    String s = new String(chars, i + 1, chars.length - i - 1);
                    map.put(s, map.getOrDefault(s, 0) + count);
                }
                if (chars[i] == '.') {
                    String s = new String(chars, i + 1, chars.length - i - 1);
                    map.put(s, map.getOrDefault(s, 0) + count);
                }
            }
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            list.add(entry.getValue() + " " + entry.getKey());
        }
        return list;
    }


    /**
     * 1742. 盒子中小球的最大数量
     *
     * @param lowLimit
     * @param highLimit
     * @return
     */
    public static int countBalls(int lowLimit, int highLimit) {
        int[] ints = new int[50];
        for (int i = lowLimit; i <= highLimit; i++) {
            int sum = 0;
            int temp = i;
            while (temp >= 10) {
                sum += temp % 10;
                temp /= 10;
            }
            sum += temp;
            ints[sum]++;
        }
        int max = 0;
        for (int anInt : ints) {
            max = Math.max(max, anInt);
        }
        return max;
    }

    /**
     * 448. 找到所有数组中消失的数字
     *
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        return null;
    }


    /**
     * 404. 左叶子之和 广度优先算法
     *
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int leftSum = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                if (node.left != null) {
                    if (node.left.left == null && node.left.right == null) {
                        leftSum += node.left.val;
                    }
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return leftSum;
    }

    /**
     * 左叶子之和
     *
     * @param root
     * @return
     */
    public int sumOfLeftLeaves2(TreeNode root) {
        return root == null ? 0 : dfs(root);
    }

    private int dfs(TreeNode node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.val : dfs(node);
        }
        if (node.right != null && !isLeafNode(node.right)) {
            ans += dfs(node.right);
        }
        return ans;
    }

    private boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }

//    public static void main(String[] args) {
//        int[] nums = {5,4,3,2,1};
//        findRelativeRanks(nums);
//
//    }


    /**
     * 506. 相对名次
     *
     * @param nums
     * @return
     */
    public static String[] findRelativeRanks(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        int maxScore = 0;
        for (int num : nums) {
            maxScore = Math.max(maxScore, num);
        }
        int[] ints = new int[maxScore + 1];
        for (int i = 0; i < nums.length; i++) {
            ints[nums[i]] = i + 1;
        }
        int index = 1;
        String[] strings = new String[nums.length];
        for (int i = ints.length - 1; i >= 0; i--) {
            if (ints[i] == 0) continue;
            String temp = null;
            if (index == 1) {
                temp = "Gold Medal";
            } else if (index == 2) {
                temp = "Silver Medal";
            } else if (index == 3) {
                temp = "Bronze Medal";
            } else {
                temp = String.valueOf(index);
            }
            strings[ints[i] - 1] = temp;
            index++;
        }
        return strings;
    }


    public List<Integer> findDisappearedNumbers2(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) return list;
        int[] arr = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]]++;
        }
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != 0) continue;
            list.add(i);
        }
        return list;
    }

//    public static void main(String[] args) {
//        int[] customers = {1,0,1,2,1,1,7,5}, grumpy = {0,1,0,1,0,1,0,1};
//        int X = 3;
//        System.out.println(maxSatisfied(customers, grumpy, X));
//    }


    /**
     * 数组+滑动窗口
     *
     * @param customers
     * @param grumpy
     * @param X
     * @return
     */
    public static int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int sum = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) sum += customers[i];
        }
        int maxSum = sum;
        for (int i = 0, len = customers.length - X; i <= len; i++) {
            int index = i;
            int count = 0;
            int tempSum = 0;
            while (count < X) {
                if (grumpy[index] == 1) {
                    tempSum += customers[index];
                }
                index++;
                count++;
            }
            maxSum = Math.max(maxSum, sum + tempSum);
        }
        return maxSum;
    }

    /**
     * 数组+滑动窗口 优化
     *
     * @param customers
     * @param grumpy
     * @param X
     * @return
     */
    public static int maxSatisfied2(int[] customers, int[] grumpy, int X) {
        int total = 0;
        int n = grumpy.length;
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                total += customers[i];
            }
        }
        int increase = 0;
        for (int i = 0; i < X; i++) {
            increase += grumpy[i] * customers[i];
        }
        int maxIncrease = increase;
        for (int i = X; i < n; i++) {
            increase = increase - customers[i - X] * grumpy[i - X] + customers[i] * grumpy[i];
            maxIncrease = Math.max(maxIncrease, increase);
        }
        return total + maxIncrease;
    }

    /**
     * 766. 托普利茨矩阵
     *
     * @param matrix
     * @return
     */
    public boolean isToeplitzMatrix(int[][] matrix) {
        if (matrix.length == 1) return true;
        int column = matrix.length;
        int row = matrix[0].length;
        for (int i = 0; i < column; i++) {
            int tempColumn = i + 1;
            int tempRow = 1;
            while (tempRow < row && tempColumn < column) {
                if (matrix[0][i] == matrix[tempRow++][tempColumn++]) return false;
            }
        }
        for (int i = column; i < column; i++) {
            int tempColumn = i + 1;
            int tempRow = 1;
            while (tempRow < row && tempColumn < column) {
                if (matrix[0][i] == matrix[tempRow++][tempColumn++]) return false;
            }
        }
        return true;
    }

//    public static void main(String[] args) {
//        findComplement(5);
//    }

    /**
     * 476. 数字的补数
     *
     * @param num
     * @return
     */
    public static int findComplement(int num) {
        int temp = num, c = 0;
        while (temp > 0) {
            temp >>= 1;
            c = (c << 1) + 1;
        }
        return num ^ c;

    }

    /**
     * 168. Excel表列名称
     *
     * @param n
     * @return
     */
    public String convertToTitle(int n) {
        if (n <= 0) return "";
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            n--;
            sb.append((char) (n % 26 + 'A'));
            n = n / 26;
        }
        return sb.reverse().toString();
    }

    /**
     * 剑指 Offer 27. 二叉树的镜像 深度优先算法
     *
     * @param root
     * @return
     */
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return root;

        return null;
    }


    /**
     * 213. 打家劫舍 II
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int first = nums[0];
        int second = nums[1];
        return 0;
    }

    /**
     * 引用计数法
     *
     * @param nums
     * @return
     */
    public int sumOfUnique(int[] nums) {
        int[] ints = new int[101];
        for (int num : nums) {
            ints[num]++;
        }
        int sum = 0;
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] == 1) sum += i;
        }
        return sum;
    }

    /**
     * map
     *
     * @param nums
     * @return
     */
    public int sumOfUnique2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) sum += entry.getKey();
        }
        return sum;
    }

//    public static void main(String[] args) {
//        int[] nums = {3, 4, 5, 1, 2};
//        System.out.println(check(nums));
//    }

    /**
     * 1752. 检查数组是否经排序和轮转得到
     *
     * @param nums
     * @return
     */
    public static boolean check(int[] nums) {
        if (nums == null || nums.length < 3) return true;
        int preNum = nums[0];
        int index = 1;
        while (index < nums.length) {
            if (preNum > nums[index]) {
                break;
            }
            preNum = nums[index++];
        }
        if (index == nums.length) return true;
        preNum = nums[index++];
        while (index < nums.length) {
            if (preNum > nums[index]) {
                break;
            }
            preNum = nums[index++];
        }
        return index == nums.length && nums[0] >= nums[nums.length - 1];
    }

    /**
     * 1768. 交替合并字符串
     *
     * @param word1
     * @param word2
     * @return
     */
    public String mergeAlternately(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        StringBuilder sb = new StringBuilder();
        int index = 0;
        while (index < chars1.length || index < chars2.length) {
            if (index < chars1.length) {
                sb.append(chars1[index]);
            }
            if (index < chars2.length) {
                sb.append(chars2[index]);
            }
            index++;
        }
        return sb.toString();
    }

//    public static void main(String[] args) {
//        System.out.println(mergeAlternately2("abcd", "pq"));
//    }

    /**
     * 1768. 交替合并字符串
     *
     * @param word1
     * @param word2
     * @return
     */
    public static String mergeAlternately2(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        StringBuilder sb = new StringBuilder();
        int index = 0;
        int len = chars1.length < chars2.length ? chars1.length : chars2.length;
        while (index < len) {
            sb.append(chars1[index]);
            sb.append(chars2[index++]);
        }
        if (chars1.length < chars2.length) {
            sb.append(new String(chars2, index, chars2.length - index));
        } else {
            sb.append(new String(chars1, index, chars1.length - index));
        }
        return sb.toString();
    }

    /**
     * 459. 重复的子字符串
     *
     * @param s
     * @return
     */
    public boolean repeatedSubstringPattern(String s) {

        return false;
    }


    /**
     * 867. 转置矩阵
     *
     * @param matrix
     * @return
     */
    public int[][] transpose(int[][] matrix) {
        int[][] arr = new int[matrix[0].length][matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                arr[j][i] = matrix[i][j];
            }
        }
        return arr;
    }

    /**
     * 118. 杨辉三角
     *
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();
        subList.add(1);
        list.add(subList);
        for (int i = 2; i <= numRows; i++) {
            List<Integer> preList = list.get(i - 1);
            subList = new ArrayList<>();
            subList.add(1);
            int preNum = preList.get(0);
            for (int j = 1, len = preList.size(); j < len; j++) {
                subList.add(preNum + preList.get(i));
                preNum = preList.get(i);
            }
            subList.add(1);
            list.add(subList);
        }
        return list;
    }

//    public static void main(String[] args) {
////        int[][] nums = {{1,2},{3,4}};
////        matrixReshape(nums, 4,1);
//        int num = 4;
//        System.out.println(num);
//        num >>= 1;
//        System.out.println(num);
//        num >>= 1;
//        System.out.println(num);
//        num >>= 1;
//        System.out.println(num);
//    }

    /**
     * 566. 重塑矩阵
     *
     * @param nums
     * @param r
     * @param c
     * @return
     */
    public static int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums.length * nums[0].length < r * c) return nums;
        int[][] arr = new int[r][c];
        int row = 0;
        int column = 0;
        for (int[] num : nums) {
            for (int i : num) {
                if (column < c) {
                    arr[row][column++] = i;
                } else {
                    row++;
                    column = 0;
                    arr[row][column++] = i;
                }
            }
        }
        return arr;
    }

    /**
     * 1770. 执行乘法运算的最大分数  贪心 + 双指针
     *
     * @param nums
     * @param multipliers
     * @return
     */
    public int maximumScore(int[] nums, int[] multipliers) {
        int firstIndex = 0;
        int endIndex = nums.length - 1;
        int sum = 0;
        for (int i = 0; i < multipliers.length; i++) {
            int firstMult = nums[firstIndex] * multipliers[i];
            int endMult = nums[endIndex] * multipliers[i];
            if (firstMult > endMult) {
                firstIndex++;
                sum += firstMult;
            } else {
                endIndex--;
                sum += endMult;
            }
        }
        return sum;
    }


    /**
     * 1770. 执行乘法运算的最大分数  动态规划
     *
     * @param nums
     * @param multipliers
     * @return
     */
    public int maximumScore2(int[] nums, int[] multipliers) {
        int firstIndex = 0;
        int endIndex = nums.length - 1;
        int sum = 0;
        for (int i = 0; i < multipliers.length; i++) {
            int firstMult = nums[firstIndex] * multipliers[i];
            int endMult = nums[endIndex] * multipliers[i];
            if (firstMult > endMult) {
                firstIndex++;
                sum += firstMult;
            } else {
                endIndex--;
                sum += endMult;
            }
        }
        return sum;
    }


    /**
     * 面试题 17.16. 按摩师
     *
     * @param nums
     * @return
     */
    public static int massage(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];
        dp[2] = nums[1];
        for (int i = 2; i < nums.length; i++) {
            dp[i + 1] = dp[i - 1] + nums[i];
        }
        return Math.max(dp[nums.length], dp[nums.length - 1]);
    }


//    public static void main(String[] args) {
//        int[] arr = {2,1,4,5,3,1,1,3};
//        System.out.println(rob2(arr));
//    }

    /**
     * 198. 打家劫舍
     *
     * @param nums
     * @return
     */
    public static int rob2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    /**
     * 198. 打家劫舍
     *
     * @param nums
     * @return
     */
    public static int rob3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int firstPre = nums[0];
        int secondPre = Math.max(nums[0], nums[1]);
        int max = secondPre;
        for (int i = 2; i < nums.length; i++) {
            max = Math.max(max, Math.max(firstPre + nums[i], secondPre));
            firstPre = secondPre;
            secondPre = max;
        }
        return max;
    }


    /**
     * @param nums
     * @return
     */
    public int rob4(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    /**
     * 748. 最短补全词
     *
     * @param licensePlate
     * @param words
     * @return
     */
    public String shortestCompletingWord(String licensePlate, String[] words) {
        char[] chars = licensePlate.toLowerCase().toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char aChar : chars) {
            if (aChar >= 97 && aChar <= 122)
                map.put(aChar, map.getOrDefault(aChar, 0) + 1);
        }
        for (String word : words) {

            chars = word.toCharArray();

        }
        return null;
    }

//    public static void main(String[] args) {
//        String[] A = {"qowfc", "spyge", "sqbif", "vvrkk"};
//        System.out.println(minDeletionSize(A));
//        StringBuilder sb = new StringBuilder();
//        System.out.println( sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null);
//    }


    /**
     * 944. 删列造序
     *
     * @param A
     * @return
     */
    public static int minDeletionSize(String[] A) {
        if (A.length == 1) return 0;
        int count = 0;
        for (int i = 0, len = A[0].length(); i < len; i++) {
            char preChar = A[0].charAt(i);
            for (int j = 1; j < A.length; j++) {
                char curChar = A[j].charAt(i);
                if (preChar > curChar) {
                    count++;
                    break;
                } else {
                    preChar = curChar;
                }
            }
        }
        return count;
    }

    /**
     * 1370. 上升下降字符串
     *
     * @param s
     * @return
     */
    public String sortString(String s) {
        char[] chars = s.toCharArray();
        int[] charArr = new int[123];
        for (char aChar : chars) {
            charArr[aChar]++;
        }
        int count = chars.length;
        StringBuilder sb = new StringBuilder();
        while (count > 0) {
            for (int i = 97; i < charArr.length; i++) {
                if (charArr[i] > 0) {
                    charArr[i]--;
                    sb.append((char) i);
                    count--;
                }
            }
            for (int i = charArr.length - 1; i >= 97; i--) {
                if (charArr[i] > 0) {
                    charArr[i]--;
                    sb.append((char) i);
                    count--;
                }
            }
        }
        return sb.toString();
    }


    /**
     * 1030. 距离顺序排列矩阵单元格
     *
     * @param R
     * @param C
     * @param r0
     * @param c0
     * @return
     */
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {

        return null;
    }

    /**
     * 1356. 根据数字二进制下 1 的数目排序
     *
     * @param arr
     * @return
     */
    public int[] sortByBits(int[] arr) {
        return null;
    }

    public int thirdMax(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        long firstMAx = Long.MIN_VALUE;
        long secondMAx = Long.MIN_VALUE;
        long thirdMAx = Long.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (firstMAx < nums[i]) {
                thirdMAx = secondMAx;
                secondMAx = firstMAx;
                firstMAx = nums[i];
            } else if (firstMAx == nums[i]) {
                continue;
            } else if (secondMAx < nums[i]) {
                thirdMAx = secondMAx;
                secondMAx = nums[i];
            } else if (secondMAx == nums[i]) {
                continue;
            } else if (thirdMAx < nums[i]) {
                thirdMAx = nums[i];
            }
        }
        return thirdMAx == Long.MIN_VALUE ? (int) firstMAx : (int) secondMAx;
    }


    public int[] printNumbers(int n) {
        int len = (int) Math.pow(10, n) - 1;
        int[] ints = new int[len];
        int count = 1;
        for (int i = 0; i < len; i++) {
            ints[i] = count++;
        }
        return ints;
    }


    /**
     * 338. 比特位计数
     *
     * @param num
     * @return
     */
    public int[] countBits(int num) {
        int[] ints = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            ints[i] = getBinaryOneCount(i);
        }
        return null;
    }

    private int getBinaryOneCount(int num) {
        int count = 0;
        while (num > 0) {
            if ((num & 1) == 1) {
                count++;
            }
            num >>= 1;
        }
        return count;
    }

//    public static void main(String[] args) {
//        ListNode listNode1 = new ListNode(1);
//        ListNode listNode2 = new ListNode(1);
//        ListNode listNode3 = new ListNode(2);
//        ListNode listNode4 = new ListNode(3);
//        ListNode listNode5 = new ListNode(3);
//        listNode1.next = listNode2;
//        listNode2.next = listNode3;
//        listNode3.next = listNode4;
//        listNode4.next = listNode5;
//        System.out.println(deleteDuplicates(listNode1));
//
//    }


    /**
     * 83. 删除排序链表中的重复元素
     *
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        int pre = head.val;
        ListNode tempFirstHead = head;
        ListNode tempHead = head.next;
        while (tempHead != null) {
            if (pre != tempHead.val) {
                tempFirstHead.next = tempHead;
                tempFirstHead = tempHead;
                pre = tempHead.val;
            }
            tempHead = tempHead.next;
        }
        return head;
    }


    /**
     * 257. 二叉树的所有路径 深度优先算法
     *
     * @param root [1,2,3,null,5]
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        constructPaths(root, "", list);
        return list;
    }

    public void constructPaths(TreeNode node, String path, List<String> list) {
        if (node != null) {
            StringBuilder stringBuilder = new StringBuilder(path);
            stringBuilder.append(node.val);
            if (node.left == null && node.right == null) {
                list.add(stringBuilder.toString());
            } else {
                stringBuilder.append("->");
                constructPaths(node.left, stringBuilder.toString(), list);
                constructPaths(node.right, stringBuilder.toString(), list);
            }
        }
    }

    /**
     * 257. 二叉树的所有路径 广度优先算法
     *
     * @param root
     * @return
     */
    public List<String> binaryTreePaths2(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQuque = new LinkedList<>();
        Queue<String> pathQuque = new LinkedList<>();

        nodeQuque.offer(root);
        pathQuque.offer(Integer.toString(root.val));

        while (!nodeQuque.isEmpty()) {
            TreeNode node = nodeQuque.poll();
            String path = pathQuque.poll();

            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQuque.offer(node.left);
                    pathQuque.offer(path + "->" + node.left.val);
                }
                if (node.right != null) {
                    nodeQuque.offer(node.right);
                    pathQuque.offer(path + "->" + node.right.val);
                }
            }
        }
        return paths;
    }

    /**
     * 461. 汉明距离
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance(int x, int y) {
        int count = 0;
        int z = x ^ y;
        while (z != 0) {
            if ((z & 1) == 1) {
                count++;
            }
            z >>= 1;
        }
        return count;
    }


//    public static void main(String[] args) {
//        addDigits(38);
//
//    }

    /**
     * 258. 各位相加
     *
     * @param num
     * @return
     */
    public static int addDigits(int num) {
        while (num > 9) {
            int temp = 0;
            for (char c : String.valueOf(num).toCharArray()) {
                temp += (c - 48);
            }
            num = temp;
        }
        return num;
    }

    /**
     * 485. 最大连续 1 的个数
     *
     * @param nums
     * @return
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        if (nums == null || nums.length == 1) {
            return 0;
        }
        int count = 0;
        int maxCount = 0;
        for (int num : nums) {
            if (num == 1) {
                count++;
            } else {
                maxCount = Math.max(count, maxCount);
                count = 0;
            }
        }
        return maxCount;
    }


    /**
     * 268. 丢失的数字
     *
     * @param nums
     * @return
     */
    public static int missingNumber(int[] nums) {
        int[] arr = new int[nums.length + 1];
        for (int num : nums) {
            arr[num]++;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) return i;
        }
        return 0;
    }

    /**
     * 268. 数学法
     *
     * @param nums
     * @return
     */
    public static int missingNumber2(int[] nums) {
        int expectSum = (nums.length + 1) >> 1;
        int factSum = 0;
        for (int num : nums) {
            factSum += num;
        }
        return expectSum - factSum;
    }

    /**
     * 331. 验证二叉树的前序序列化
     *
     * @param preorder
     * @return
     */
    public boolean isValidSerialization(String preorder) {

        return false;
    }

    /**
     * 219. 存在重复元素 II
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
                continue;
            }
            if (Math.abs(map.get(nums[i]) - i) <= k) {
                return true;
            }
        }
        return false;
    }


    /**
     * 1784. 检查二进制字符串字段
     *
     * @param s
     * @return
     */
    public boolean checkOnesSegment(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        int preIndex = 0;
        boolean flag = false;
        for (int i = 1; i < chars.length; i++) {
            if (count > 1) return false;
            if (chars[i] == '0') {
                flag = true;
                if (i - preIndex - 1 > 0) {
                    count++;
                }
                preIndex = i;
            } else {

            }
        }
        return count == 1;
    }

//    public static void main(String[] args) {
//        int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
//        int[][] arr2 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
//        spiralOrder(arr);
//        spiralOrder(arr2);
//    }

    /**
     * 54. 螺旋矩阵
     *
     * @param matrix
     * @return
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int higth = matrix.length;
        int width = matrix[0].length;
        int hStart = 0, hEnd = higth - 1;
        int wStart = 0, wEnd = width - 1;
        while (hStart <= hEnd && wStart <= wEnd) {
            for (int i = wStart; i <= wEnd; i++) {
                list.add(matrix[hStart][i]);
            }
            for (int i = hStart + 1; i <= hEnd; i++) {
                list.add(matrix[i][wEnd]);
            }
            if (wStart < wEnd && hStart < hEnd) {
                for (int i = wEnd - 1; i > hStart; i--) {
                    list.add(matrix[hEnd][i]);
                }
                for (int i = hEnd; i > hStart; i--) {
                    list.add(matrix[i][wStart]);
                }
            }
            wStart++;
            hStart++;
            wEnd--;
            hEnd--;

        }
        return list;

    }

//    public static void main(String[] args) {
//        generateMatrix(5);
//    }


    /**
     * 59. 螺旋矩阵 II
     *
     * @param n
     * @return
     */
    public static int[][] generateMatrix(int n) {
        int[][] arr = new int[n][n];
        int left = 0;
        int right = n - 1;
        int top = 0;
        int bottom = right;
        int idxValue = 1;
        while (left < right && top < bottom) {
            for (int i = left; i < right; i++) {
                arr[top][i] = idxValue++;
            }
            for (int i = top; i < bottom; i++) {
                arr[i][right] = idxValue++;
            }
            for (int i = right; i > left; i--) {
                arr[bottom][i] = idxValue++;
            }
            for (int i = bottom; i > top; i--) {
                arr[i][left] = idxValue++;
            }
            left++;
            top++;
            bottom--;
            right--;
        }
        if (left == right && top == bottom) {
            arr[left][top] = idxValue++;
        }
        return arr;
    }


    /**
     * 面试题 08.10. 颜色填充
     *
     * @param image
     * @param sr
     * @param sc
     * @param newColor
     * @return
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        floodFillDFS(sr, sc, image, image[sr][sc], newColor);
        return image;
    }

    private void floodFillDFS(int sr, int sc, int[][] image, int originColor, int newColor) {
        if (originColor == newColor || sr >= image.length || sr < 0 || sc >= image[0].length || sc < 0) {
            return;
        }
        if (image[sr][sc] == originColor) {
            image[sr][sc] = newColor;
            floodFillDFS(sr + 1, sc, image, originColor, newColor);
            floodFillDFS(sr - 1, sc, image, originColor, newColor);
            floodFillDFS(sr, sc + 1, image, originColor, newColor);
            floodFillDFS(sr, sc - 1, image, originColor, newColor);
        }
    }

//    public static void main(String[] args) {
//        int[] A = {1, 7, 8, 0, 0, 0};
//        int[] B = {2, 5, 6};
//        merge2(A, 3, B, 3);
//    }


    /**
     * 面试题 10.01. 合并排序的数组
     *
     * @param A
     * @param m
     * @param B
     * @param n
     */
    public static void merge(int[] A, int m, int[] B, int n) {
        int bIndex = 0;
        for (int i = m; i < A.length; i++) {
            A[i] = B[bIndex++];
        }
        Arrays.sort(A);
    }

    public static void merge2(int[] A, int m, int[] B, int n) {
        int aIdx = m - 1, bIdx = n - 1, curIdx = m + n - 1;
        int cur;
        while (aIdx >= 0 || bIdx >= 0) {
            if (aIdx == -1) {
                cur = B[bIdx--];
            } else if (bIdx == -1) {
                cur = A[aIdx--];
            } else if (A[aIdx] > B[bIdx]) {
                cur = A[aIdx--];
            } else {
                cur = B[bIdx--];
            }
            A[curIdx--] = cur;
        }

    }

//    public static void main(String[] args) {
//        System.out.println(kdxf01("abbccccaaddaggb"));
//    }


    public static String kdxf01(String str) {
        int[] ints = new int[123];
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char aChar : chars) {
            if (ints[aChar] == 0) {
                ints[aChar] = 1;
                sb.append(aChar);
            }
        }
        return sb.toString();
    }


    /**
     * 278. 第一个错误的版本
     *
         * @param
     * @return
     */
//    public int firstBadVersion(int n) {
//        if (n == 1) return 1;
//        int start = 1;
//        while (start <= n) {
//            int mid = (start + n) >> 1;
//            if (isBadVersion(mid)) {
//                if (isBadVersion(mid - 1)) {
//                    return mid;
//                }
//                start = mid;
//            } else {
//                n = mid;
//            }
//        }
//        return start;
//    }

    public int minOperations(String s) {
        char[] chars = s.toCharArray();
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < chars.length; i++) {
            if ((i & 1) == 0) {
                if (chars[i] == '0') {
                    count1++;
                } else {
                    count2++;
                }
            } else {
                if (chars[i] == '1') {
                    count1++;
                } else {
                    count2++;
                }
            }
        }
        return Math.min(count1, count2);

    }


    /**
     * 面试题 05.07. 配对交换
     *
     * @param num
     * @return
     */
    public int exchangeBits(int num) {
        return ((num & 0x55555555) << 1) | ((num & 0xaaaaaaaa) >> 1);
    }

    /**
     * 面试题 04.02. 最小高度树
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (right - left) / 2 + left;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, left, mid - 1);
        node.right = helper(nums, mid + 1, right);
        return node;
    }

//    public static void main(String[] args) {
//        countAndSay(3);
//    }


    /**
     * 38. 外观数列
     *
     * @param n
     * @return
     */
    public static String countAndSay(int n) {
        if (n == 1) return "1";
        if (n == 2) return "11";
        int count = 3;
        String prestr = "11";
        while (count++ <= n) {
            char[] chars = prestr.toCharArray();
            StringBuilder sb = new StringBuilder();
            char preChar = chars[0];
            int tempCount = 1;
            for (int i = 1; i < chars.length; i++) {
                if (preChar == chars[i]) {
                    tempCount++;
                } else {
                    sb.append(tempCount).append(preChar);
                    preChar = chars[i];
                    tempCount = 1;
                }
            }
            sb.append(tempCount).append(preChar);
            prestr = sb.toString();
        }
        return prestr;
    }

    public static void main(String[] args) {
        addBinary("11", "11");
    }


    /**
     * 67. 二进制求和
     *
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();
        StringBuilder sb = new StringBuilder();
        int aIndex = aChars.length - 1, bIndex = bChars.length - 1;
        char preValue = '0';
        while (aIndex >= 0 || bIndex >= 0) {
            int count = 0;
            count += preValue == '1' ? 1 : 0;
            if (aIndex == -1) {
                count += bChars[bIndex--] == '1' ? 1 : 0;
            } else if (bIndex == -1) {
                count += aChars[aIndex--] == '1' ? 1 : 0;
            } else {
                count += aChars[aIndex--] == '1' ? 1 : 0;
                count += bChars[bIndex--] == '1' ? 1 : 0;
            }
            if (count == 0) {
                preValue = '0';
                sb.append(0);
            } else if (count == 1) {
                preValue = '0';
                sb.append(1);
            } else if (count == 2) {
                preValue = '1';
                sb.append(0);
            } else {
                preValue = '1';
                sb.append(1);
            }
        }
        if (preValue == '1') {
            sb.append(1);
        }
        return sb.reverse().toString();
    }
}

class NumArray {

    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

class NumMatrix {

    private int[][] matrix;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                sum += matrix[i][j];
            }
        }
        return sum;
    }
}


class ParkingSystem {
    private int[] arr;

    public ParkingSystem(int big, int medium, int small) {
        arr = new int[4];
        arr[1] = big;
        arr[2] = medium;
        arr[3] = small;
    }

    public boolean addCar(int carType) {
        if (arr[carType] > 0) {
            arr[carType]--;
            return true;
        }
        return false;
    }
}
